#pragma once
#include<assert.h>
template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;//balance factor
	pair<K, V> _kv;

	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{ }
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root==nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if(cur->kv.first>kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->kv.first<kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->parent = parent;

		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = cur->_parent;

				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//
				//

				break;
			}
			else
			{
				
			}
		}

		return true;
	}
	
	void RotateL(Node* parent)
	{
		Node* sunR=parent->_right;
		Node* sunRL=sunR->_left;

		parent->_right = sunRL;
		if (sunRL)
			sunRL->_parent = parent;

		sunR->_left = parent;
		Node* ppnode = parent->_parent;
		parent->_left = sunR;

		if (parent==_root)
		{
			_root = sunR;
			sunR->_parent;
		}
		else
		{
			if (ppnode->_left==parent)
			{
				ppnode->_left = sunR;
			}else
			{
				ppnode->_right = sunR;
			}
			sunR->_parent = ppnode;
		}
		parent->_bf = 0;
		sunR->_bf = 0;
	}
private:
	Node* _root;
};

